package cn.aylog.simpleTree;

/**
 * 线索化二叉树
 * 1、节点的leftNode指向前驱节点
 * 2、节点的rightNode指向后继节点
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        ThreadedBinaryTree tree = new ThreadedBinaryTree();
        ThreadedHeroNode node1 = new ThreadedHeroNode(1, "宋江");
        ThreadedHeroNode node2 = new ThreadedHeroNode(2, "吴用");
        ThreadedHeroNode node3 = new ThreadedHeroNode(3, "卢俊义");
        ThreadedHeroNode node4 = new ThreadedHeroNode(4, "林冲");
        ThreadedHeroNode node5 = new ThreadedHeroNode(5, "鲁智深");
        ThreadedHeroNode node6 = new ThreadedHeroNode(6, "武松");

        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        tree.setRoot(node1);

        // tree.doPreThreaded();
        // tree.doInfixThreaded();
        tree.dpPostThreaded();
        System.out.println("线索化遍历");
        tree.doThreadedOrder();
    }
}

enum NodeType {
    NODE, // 前驱/后继节点
    TREE // 树节点
}

/**
 * 线索化树
 */
class ThreadedBinaryTree {
    private ThreadedHeroNode root;

    public void setRoot(ThreadedHeroNode root) {
        this.root = root;
    }

    public void preOrder() {
        if (root != null) root.preOrder();
    }

    public void infixOrder() {
        if (root != null) root.infixOrder();
    }

    public void postOrder() {
        if (root != null) root.postOrder();
    }

    public ThreadedHeroNode preOrderSearch(int id) {
        if (root != null) return root.preOrderSearch(id);
        return null;
    }

    public ThreadedHeroNode infixOrderSearch(int id) {
        if (root != null) return root.infixOrderSearch(id);
        return null;
    }

    public ThreadedHeroNode postOrderSearch(int id) {
        if (root != null) return root.postOrderSearch(id);
        return null;
    }

    public ThreadedHeroNode del(int id) {
        ThreadedHeroNode delNode = null;
        if (root != null) {
            if (root.getId() == id) {
                delNode = root;
                root = null;
            } else {
                delNode = root.del(id);
            }
        }
        return delNode;
    }

    public void add(ThreadedHeroNode node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void doInfixThreaded() {
        if (root != null) {
            root.doInfixThreaded();
        }
    }

    public void doPreThreaded() {
        if (root != null) {
            root.doPreThreaded();
        }
    }

    public void dpPostThreaded() {
        if (root != null) {
            root.doPostThread();
        }
    }

    /**
     * 线索化遍历
     */
    public void doThreadedOrder() {
        ThreadedHeroNode node = root;
        // 找到起始节点
        while (node.getLeftNode() != null || node.getLeftNodeType() == NodeType.TREE) {
            node = node.getLeft();
        }
        System.out.println(node);
        // 遍历输出后续节点
        while (node.getRightNodeType() == NodeType.NODE) {
            node = node.getRightNode();
            System.out.println(node);
        }
    }
}

/**
 * 线索化节点
 */
class ThreadedHeroNode {
    private int id;
    private String name;
    private ThreadedHeroNode left;
    private ThreadedHeroNode right;
    private ThreadedHeroNode leftNode;
    private ThreadedHeroNode rightNode;

    public ThreadedHeroNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(ThreadedHeroNode leftNode) {
        this.leftNode = leftNode;
    }

    public ThreadedHeroNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(ThreadedHeroNode rightNode) {
        this.rightNode = rightNode;
    }

    private NodeType leftNodeType = NodeType.TREE; // 节点类型
    private NodeType rightNodeType = NodeType.TREE;

    private static ThreadedHeroNode pre; // 指向前一个节点

    public NodeType getLeftNodeType() {
        return leftNodeType;
    }

    public void setLeftNodeType(NodeType leftNodeType) {
        this.leftNodeType = leftNodeType;
    }

    public NodeType getRightNodeType() {
        return rightNodeType;
    }

    public void setRightNodeType(NodeType rightNodeType) {
        this.rightNodeType = rightNodeType;
    }

    public ThreadedHeroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public ThreadedHeroNode getLeft() {
        return left;
    }

    public void setLeft(ThreadedHeroNode left) {
        this.left = left;
    }

    public ThreadedHeroNode getRight() {
        return right;
    }

    public void setRight(ThreadedHeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "ThreadedHeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 中序节点线索化（左根右）
     */
    public void doInfixThreaded() {
        if (this.left != null) {
            this.left.doInfixThreaded();
        }

        if (this.left == null) {
            this.leftNode = pre;
            this.leftNodeType = NodeType.NODE;
        }

        if (pre != null) {
            pre.rightNode = this;
            pre.rightNodeType = NodeType.NODE;
        }

        pre = this;

        if (this.right != null) {
            this.right.doInfixThreaded();
        }
    }

    /**
     * 前序节点线索化（根左右）
     */
    public void doPreThreaded() {
        this.leftNode = pre;
        this.leftNodeType = NodeType.NODE;
        if (pre != null) {
            pre.rightNode = this;
            pre.rightNodeType = NodeType.NODE;
        }
        pre = this;

        if (this.left != null) {
            this.left.doPreThreaded();
        }
        if (this.right != null) {
            this.right.doPreThreaded();
        }
    }

    /**
     * 后序节点线索化
     */
    public void doPostThread() {
        if (this.left != null) {
            this.left.doPostThread();
        }
        if (this.right != null) {
            this.right.doPostThread();
        }
        if (this.left == null) {
            this.leftNode = pre;
            this.leftNodeType = NodeType.NODE;
        }

        if (pre != null) {
            pre.rightNode = this;
            pre.rightNodeType = NodeType.NODE;
        }
        pre = this;
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) this.left.preOrder();
        if (this.right != null) this.right.preOrder();
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.left != null) this.left.infixOrder();
        System.out.println(this);
        if (this.right != null) this.right.infixOrder();
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        if (this.left != null) this.left.postOrder();
        if (this.right != null) this.right.postOrder();
        System.out.println(this);
    }

    /**
     * 前序查找
     */
    public ThreadedHeroNode preOrderSearch(int id) {
        if (this.id == id) return this;
        ThreadedHeroNode ret = null;
        if (this.left != null) ret = this.left.preOrderSearch(id);
        if (ret != null) return ret;
        if (this.right != null) ret = this.right.preOrderSearch(id);
        return ret;
    }

    /**
     * 中序查找
     */
    public ThreadedHeroNode infixOrderSearch(int id) {
        ThreadedHeroNode ret = null;
        if (this.left != null) ret = this.left.infixOrderSearch(id);
        if (ret != null) return ret;
        if (this.id == id) return this;
        if (this.right != null) ret = this.right.infixOrderSearch(id);
        return ret;
    }

    /**
     * 后序查找
     */
    public ThreadedHeroNode postOrderSearch(int id) {
        ThreadedHeroNode ret = null;
        if (this.left != null) ret = this.left.postOrderSearch(id);
        if (ret != null) return ret;
        if (this.right != null) ret = this.right.postOrderSearch(id);
        if (ret != null) return ret;
        if (this.id == id) return this;
        return null;
    }

    /**
     * 节点删除, 直接删除节点或数,不考虑移动
     */
    public ThreadedHeroNode del(int id) {
        ThreadedHeroNode delNode = null;
        if (this.left != null) {
            if (this.left.id == id) {
                ThreadedHeroNode ret = this.left;
                this.left = null;
                return ret;
            } else {
                delNode = this.left.del(id);
            }
        }
        if (delNode != null) {
            return delNode;
        }

        if (this.right != null) {
            if (this.right.id == id) {
                ThreadedHeroNode ret = this.right;
                this.right = null;
                return ret;
            } else {
                delNode = this.right.del(id);
            }
        }
        return delNode;

        // if(this.left!=null && this.left.id != id) {
        //     this.left.del(id);
        // } else {
        //     this.left = null;
        // }
        //
        // if(this.right!=null && this.right.id != id) {
        //     this.right.del(id);
        // } else {
        //     this.right = null;
        // }
    }

    /**
     * 节点新增
     */
    public void add(ThreadedHeroNode node) {
        if (this.id <= node.id) {
            if (this.right != null) {
                this.right.add(node);
            } else {
                this.right = node;
            }
        } else {
            if (this.left != null) {
                this.left.add(node);
            } else {
                this.left = node;
            }
        }
    }
}

